In mathematics and economics, transportation theory is a name given to the study of optimal transportation and allocation of resources.
The problem was formalized by the French mathematician Gaspard Monge in 1781.[1]
In the 1920s A.N. Tolstoi was one of the first to study the transportation problem mathematically. In 1930, in the collection Transportation Planning Volume I for the National Commissariat of Transportation of the Soviet Union, he published a paper "Methods of Finding the Minimal Kilometrage in Cargo-transportation in space".[2][3]
Major advances were made in the field during World War II by the Soviet/Russian mathematician and economist Leonid Kantorovich.[4] Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem.
Contents |
Suppose that we have a collection of n mines mining iron ore, and a collection of n factories which consume the iron ore that the mines produce. Suppose for the sake of argument that these mines and factories form two disjoint subsets M and F of the Euclidean plane R2. Suppose also that we have a cost function c : R2 × R2 → [0, ∞), so that c(x, y) is the cost of transporting one shipment of iron from x to y. For simplicity, we ignore the time taken to do the transporting. We also assume that each mine can supply only one factory (no splitting of shipments) and that each factory requires precisely one shipment to be in operation (factories cannot work at half- or double-capacity). Having made the above assumptions, a transport plan is a bijection — i.e. an arrangement whereby each mine supplies precisely one factory . We wish to find the optimal transport plan, the plan whose total cost
is the least of all possible transport plans from to . This motivating special case of the transportation problem is in fact an instance of the assignment problem.
The following simple example illustrates the importance of the cost function in determining the optimal transport plan. Suppose that we have n books of equal width on a shelf (the real line), arranged in a single contiguous block. We wish to rearrange them into another contiguous block, but shifted one book-width to the right. Two obvious candidates for the optimal transport plan present themselves:
If the cost function is proportional to Euclidean distance (c(x, y) = α |x − y|) then these two candidates are both optimal. If, on the other hand, we choose the strictly convex cost function proportional to the square of Euclidean distance (), then the "many small moves" option becomes the unique minimizer.
Interestingly, while mathematicians prefer to work with convex cost functions, economists prefer concave ones. The intuitive justification for this is that once goods have been loaded on to, say, a goods train, transporting the goods 200 kilometres costs much less than twice what it would cost to transport them 100 kilometres. Concave cost functions represent this economy of scale.
The transportation problem as it is stated in modern or more technical literature looks somewhat different because of the development of Riemannian geometry and measure theory. The mines-factories example, simple as it is, is a useful reference point when thinking of the abstract case. In this setting, we allow the possibility that we may not wish to keep all mines and factories open for business, and allow mines to supply more than one factory, and factories to accept iron from more than one mine.
Let and be two separable metric spaces such that any probability measure on (or ) is a Radon measure (i.e. they are Radon spaces). Let be a Borel-measurable function. Given probability measures on and on , Monge's formulation of the optimal transportation problem is to find a transport map that realizes the infimum
where denotes the push forward of by . A map that attains this infimum (i.e. makes it a minimum instead of an infimum) is called an "optimal transport map".
Monge's formulation of the optimal transportation problem can be ill-posed, because sometimes there is no satisfying : this happens, for example, when is a Dirac measure but is not).
We can improve on this by adopting Kantorovich's formulation of the optimal transportation problem, which is to find a probability measure on that attains the infimum
where denotes the collection of all probability measures on with marginals on and on . It can be shown[5] that a minimizer for this problem always exists when the cost function is lower semi-continuous and is a tight collection of measures (which is guaranteed for Radon spaces and ). (Compare this formulation with the definition of the Wasserstein metric on the space of probability measures.)
The minimum of the Kantorovich problem is equal to
where the supremum runs over all pairs of bounded and continuous functions and such that
For , let denote the collection of probability measures on that have finite th moment. Let and let , where is a convex function.
Let be a separable Hilbert space. Let denote the collection of probability measures on such that have finite th moment; let denote those elements that are Gaussian regular: if is any strictly positive Gaussian measure on and , then also.
Let , , for , . Then the Kantorovich problem has a unique solution , and this solution is induced by an optimal transport map: i.e., there exists a Borel map such that
Moreover, if has bounded support, then
for some locally Lipschitz, c-concave and maximal Kantorovich potential . (Here denotes the Gâteaux derivative of .)
Media related to [//commons.wikimedia.org/wiki/Category:Transportation_theory Transportation theory] at Wikimedia Commons